package d_binary_search_tree;

import d_binary_search_tree.a_binary_search.BinarySearchTree;

public class MainTest {

    public static void main(String[] args) {
        System.out.println("\n---------------基本api-------------------");
        BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
        System.out.println(bst.isEmpty());
        System.out.println(bst.size());

        // 添加顺序
        Integer[] source = {8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15, 0, 16};
        // Integer[] source = {4, 2, 1, 3, 0, 11, 5, 10, 9, 8, 7, 6, 13, 12, 14, 15,16};
        for (int i = 0; i < source.length; i++) {
            int key = source[i];
            bst.insert(key, "item-" + key);
            if (bst.containKey(key))
                System.out.print(key + "->" + bst.findValueByKey(key) + "\t");
        }

        System.out.println();
        System.out.println("min key: " + bst.getMinKey());
        System.out.println("max key: " + bst.getMaxKey());
        // bst.removeMin();
        bst.removeByKey(0);
        // bst.removeMax();
        bst.removeByKey(16);
        System.out.println("前驱测试");
        System.out.println(bst.predecessor(1)); // null
        System.out.println(bst.predecessor(15)); // 14
        System.out.println(bst.predecessor(5)); // 4
        System.out.println(bst.predecessor(6)); // 5
        System.out.println(bst.predecessor(11)); // 10
        System.out.println("后继测试");
        System.out.println(bst.successor(1)); // 2
        System.out.println(bst.successor(15)); // null
        System.out.println(bst.successor(5)); // 6
        System.out.println(bst.successor(11)); // 12
        //                                   8
        //                         4                    12
        //                    2        6          10         14
        //                 1    3    5    7    9     11    13   15
        System.out.println("\n---------------深度优先遍历-------------------");

        System.out.println("前序遍历");
        bst.preOrder();
        System.out.println("中序遍历");
        bst.inOrder();
        System.out.println("后序遍历");
        bst.postOrder();

        System.out.println("\n---------------广度优先遍历-------------------");

        bst.levelOrder();

    }
}
